package leetcode;

import java.util.ArrayList;
import java.util.List;

public class CountSmallerNumbersAfterSelf {

	// 使用线段树求解
	public static void main(String[] args) {
		CountSmallerNumbersAfterSelf object = new CountSmallerNumbersAfterSelf();
		int[] nums = { 5, 4, 3, 6, 7, 1 };
		System.out.println(object.countSmaller(nums));
	}

	int[] segmentTree;
	int[] nums;

	// 感觉是对区间更新
	public List<Integer> countSmaller(int[] nums) {
		this.nums = nums;
		segmentTree = new int[nums.length * 4];
		build(0, 0, nums.length - 1);
		List<Integer> res = new ArrayList<>();
		for (int i = 0; i < nums.length - 1; i++) {
			update(0, 0, nums.length - 1, i + 1, nums.length - 1, nums[i]);
			res.add(query(0, 0, nums.length - 1, i + 1, nums.length - 1));
		}
		res.add(0);
		return res;
	}

	// 初始都是0
	public void build(int num, int left, int right) {

	}

	public void update(int num, int left, int right, int x, int y, int lessthan) {
		// System.out.println("num: " + num);
		if (right == left) {
			segmentTree[num] = nums[left] < lessthan ? 1 : 0;
			// System.out.println("num: " + num + " left : " + left + " value:"
			// + segmentTree[num]);
			return;
		}
		int mid = (left + right) / 2;
		if (x <= mid) {
			update(num * 2 + 1, left, mid, x, y, lessthan);
		}
		if (y > mid) {
			update(num * 2 + 2, mid + 1, right, x, y, lessthan);
		}
		segmentTree[num] = segmentTree[num * 2 + 1] + segmentTree[num * 2 + 2];
	}

	public int query(int num, int left, int right, int x, int y) {
		// 如果满足该条件，此时tree[num]就已经是这一部分的有效数据了，所以直接return即可
		if (x <= left && y >= right) {
			return segmentTree[num];
		}
		int mid = (left + right) / 2;
		int ans = 0;
		if (x <= mid)
			ans += query(num * 2 + 1, left, mid, x, y);
		if (y > mid)
			ans += query(num * 2 + 2, mid + 1, right, x, y);
		return ans;
	}
}
